package greedy

import "sort"

func findContentChildren() {
	findContentChildrenHelper([]int{1, 2, 3}, []int{1, 1})
	findContentChildrenHelper([]int{1, 2}, []int{1, 2, 3})

}

func findContentChildrenHelper(g []int, s []int) int {
	sort.Ints(g)
	sort.Ints(s)
	child, cookie := 0, 0
	for child < len(g) && cookie < len(s) {
		if g[child] <= s[cookie] {
			child++
		}
		cookie++
	}
	return child
}

func canJump() {
	canJumpHepler([]int{2, 3, 1, 1, 4})
	canJumpHepler([]int{3, 2, 1, 0, 4})
}

func canJumpHepler(nums []int) bool {
	maxJump := 0
	for i, num := range nums {
		if i > maxJump {
			return false
		}
		if i+num > maxJump {
			maxJump = i + num
		}
	}
	return true
}

func knapsack() {
	knapsackHelper([]int{1, 3, 4}, []int{15, 20, 30}, 4)
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func knapsackHelper(weights []int, values []int, capacity int) int {
	n := len(weights)
	dp := make([][]int, n+1)
	for i := range dp {
		dp[i] = make([]int, capacity+1)
	}

	for i := 1; i <= n; i++ {
		for j := 1; j <= capacity; j++ {
			if j < weights[i-1] {
				dp[i][j] = dp[i-1][j]
			} else {
				dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]]+values[i-1])
			}
		}
	}

	return dp[n][capacity]
}
